import java.util.Arrays;

public class J092101 {
    public static void mergeSort(int[] nums){
        if(nums.length == 0){
            return;
        }
        int[] copynums = Arrays.copyOf(nums,nums.length);
        normalMergeSort(copynums);
        System.out.println(Arrays.toString(copynums));
        int right = nums.length;
        recursionMergeSort(nums, 0, right - 1);
    }
    public static void normalMergeSort(int[] nums){
        int tmplen = 1;
        int len = nums.length;
        while(tmplen < len){
            for(int i = 0; i < len; i += 2*tmplen){
                int left = i;
                int right = left + tmplen - 1;
                int left2 = left + tmplen;
                int right2 = left2 + tmplen - 1;
                if(left2 >= len){
                    break;
                }
                if(right2 >= len){
                    right2 = len - 1;
                }
                collect(nums, left, right, left2, right2);
            }
            tmplen *= 2;
            if(tmplen > len){
                tmplen = len;
            }
        }
    }
    public static void recursionMergeSort(int[] nums, int left, int right){
        if(left == right){
            return;
        }
        int key = (left + right) / 2;
        recursionMergeSort(nums,left,key);
        recursionMergeSort(nums,key + 1, right);
        collect(nums, left, key, key + 1, right);
    }
    public static void collect(int[] nums,int left1, int right1, int left2, int right2){
        int start = 0;
        int flage = left1;
        int[] tmpnums = new int[right1 - left1 + right2 - left2 + 2];
        while(left1 <= right1 && left2 <= right2){
            if(nums[left1] <= nums[left2]){
                tmpnums[start++] = nums[left1];
                left1++;
            }else{
                tmpnums[start++] = nums[left2];
                left2++;
            }
        }
        if(left1 > right1){
            while(left2 <= right2){
                tmpnums[start++] = nums[left2++];
            }
        }else{
            while(left1 <= right1) {
                tmpnums[start++] = nums[left1++];
            }
        }
        for(int i = 0; i < tmpnums.length; i++){
            nums[flage++] = tmpnums[i];
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{5,2,13,4,15,6,16,7,18,9,1,12,2,13,3,14,4,15,5,16,6,17,7,18,8,19};
        mergeSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
